////////////////////////////////////////////////////////////////////////////////////////////////////
/// Copyright (c) 2009 - 2010 RacoonStudios
///
/// Permission is hereby granted, free of charge, to any person obtaining a copy of this
/// software and associated documentation files (the "Software"), to deal in the Software
/// without restriction, including without limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
/// to whom the Software is furnished to do so, subject to the following conditions:
///
/// The above copyright notice and this permission notice shall be included in all copies or
/// substantial portions of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
/// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
/// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
/// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
/// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
////////////////////////////////////////////////////////////////////////////////////////////////////

#pragma once
#ifndef fixedarray_h__
#define fixedarray_h__

#include "core/types.h"
#include "helper/array.h"

namespace Helper
{
	////////////////////////////////////////////////////////////////////////////////////////////////////
	/// \class	FixedArray
	///
	/// \brief	A FixedArray is nearly just the same as a normal Array.
	///			The only main difference is that here we have no dynamic growing
	///			but a fixed size. When we want to resize the FixedArray we will lose
	///			every binding to any object within the FixedArray.
	///
	/// \author	khaos
	/// \date	14.12.2009
	////////////////////////////////////////////////////////////////////////////////////////////////////
	template<class T>
	class FixedArray
	{
		public:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \typedef	void * Iterator
			///
			/// \brief	An Iterator for the FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			typedef void * Iterator;




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	FixedArray()
			///
			/// \brief	Default constructor. 
			///
			/// \author	Khaos
			/// \date	02.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			FixedArray();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	FixedArray(tSize size)
			///
			/// \brief	Constructor. 
			///
			/// \author	Khaos
			/// \date	02.01.2010
			///
			/// \param	[in]	size	The size of the FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			FixedArray(tSize size);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	FixedArray(tSize size, const T & element)
			///
			/// \brief	Constructor. 
			///
			/// \author	Khaos
			/// \date	02.01.2010
			///
			/// \param	[in]	size	The size of the FixedArray.
			/// \param	[in]	element	The element we want to fill in every gap.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			FixedArray(tSize size, const T & element);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	FixedArray(const FixedArray<T> & rhs)
			///
			/// \brief	Constructor. 
			///
			/// \author	Khaos
			/// \date	02.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			FixedArray(const FixedArray<T> & rhs);





			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void operator= (const FixedArray<T> & rhs)
			///
			/// \brief	Copy operator. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void operator = (const FixedArray<T> & rhs);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool operator== (const FixedArray<T> & rhs) const
			///
			/// \brief	Equality operator. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			///
			/// \return	True if both objects are equal, otherwise fale.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool operator == (const FixedArray<T> & rhs) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool operator!= (const FixedArray<T> & rhs) const
			///
			/// \brief	Inequality operator. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			///
			/// \return	True if both objects are inequal, otherwise false.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool operator != (const FixedArray<T> & rhs) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	const T & operator[] (tIndex index) const
			///
			/// \brief	Casting operator. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	index	The position of the element we want.
			///
			/// \return	The element of the specified position we want to receive.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			const T & operator [] (tIndex index) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	T & operator[] (tIndex index)
			///
			/// \brief	Casting operator. 
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	index	The position of the element we want.
			///
			/// \return	The element of the specified position we want to receive. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			T & operator [] (tIndex index);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void SetSize(tSize newSize)
			///
			/// \brief	Here we set a new size for the whole FixedArray.
			///			But keep in mind that all elements of the FixedArray will be erased
			///			as well when you use this procedure.
			///			If you don't want to lose them use Reset(SIZE). 
			///
			/// \author	khaos
			/// \date	14.12.2009
			///
			/// \param	[in]	newSize	Size of the new. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void SetSize(tSize newSize);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tSize Size() const
			///
			/// \brief	Returns the size of the FixedArray.
			///
			/// \author	Khaos
			/// \date	02.01.2010
			///
			/// \return	The size of the FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tSize Size() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	bool IsEmpty() const
			///
			/// \brief	Determines if this object is empty.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	True if the FixedArray is emoty, otherwise false.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			bool IsEmpty() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Reset(tSize newsize)
			///
			/// \brief	Very similar to SetSize() but the main difference is that the new FixedArray
			///			we produce with this procedure contains all elements of the old FixedArray.
			///			So you don't lose any element and just resize the FixedArray.
			///			If you also want to erase all containing object you have to use the Clear
			///			procedure. Within this one we also release all contained objects.
			///
			/// \author	khaos
			/// \date	14.12.2009
			///
			/// \param	[in]	newsize	The new size the FixedArray should have.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Reset(tSize newsize);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Clear()
			///
			/// \brief	Clears the whole FixedArray. We also call the destructors of every
			///			objects.
			///
			/// \author	Markus
			/// \date	22.01.2010
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Clear();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Fill(const T & element)
			///
			/// \brief	Fills the whole FixedArray with just this element.
			///
			/// \author	khaos
			/// \date	14.12.2009
			///
			/// \param	[in]	element	The element we want to fill in every gap of the
			///					FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Fill(const T & element);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Fill(tSize start, tSize num, const T & element)
			///
			/// \brief	Fills the specified amount of elements at the specified startr position
			///			with this element.
			///
			/// \author	khaos
			/// \date	14.12.2009
			///
			/// \param	[in]	start	The index where we start filling in the elements.
			/// \param	[in]	num		The number of elements we want to fill.
			/// \param	[in]	element	The element we want to fill in the gaps.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Fill(tSize start, tSize num, const T & element);




			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Iterator Begin() const
			///
			/// \brief	Returns an Iterator pointing to the first element of the FixedArray.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	The first element of the FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Iterator Begin() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Iterator End() const
			///
			/// \brief	Returns an Iterator pointing to the last element of the FixedArray.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	The last element of the FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Iterator End() const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Iterator Find(const T & element)
			///
			/// \brief	Searches for the specified element within the FixedArray.
			///			If the FixedArray contains the element we will returns an Iterator
			///			pointing towards it. If we don't find any element we just return
			///			a NULL pointer.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	element	The element we are looking for. 
			///
			/// \return	Returns an Iterator pointing towards the element if valid, otherwise 
			///			we return a NULL pointer.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Iterator Find(const T & element);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tIndex FindIndex(const T & element)
			///
			/// \brief	Searches for the specified element.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	element	The element we are looking for. 
			///
			/// \return	The index of the element we are looking for if its within the FixedArray,
			///			otherwise InvalidIndex (-1).
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tIndex FindIndex(const T & element);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	tIndex BinarySearchIndex(const T & element) const
			///
			/// \brief	Just do a binary search, just like the one known from the Array class.
			///			I really do just a copy&paste here :D
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	element	The element we are looking for. 
			///
			/// \return	The index of the object if found, otherwise InvalidIndex (-1).
			////////////////////////////////////////////////////////////////////////////////////////////////////
			tIndex BinarySearchIndex(const T & element) const;

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	Array<T> GetAsArray() const
			///
			/// \brief	Returns all elements of the FixedArray packed in an Array.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \return	Returns an Array containing all elements of this FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			Array<T> GetAsArray() const;

		protected:

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Delete()
			///
			/// \brief	Deletes this FixedArray and all of the elements stored  within.
			///
			/// \author	khaos
			/// \date	14.12.2009
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Delete();

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Alloc(tSize size)
			///
			/// \brief	Allocates new memory for the FixedArray.
			///
			/// \author	khaos
			/// \date	14.12.2009
			///
			/// \param	[in]	size	The size we want to reserve for this FixedArray.
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Alloc(tSize size);

			////////////////////////////////////////////////////////////////////////////////////////////////////
			/// \fn	void Copy(const FixedArray<T> & rhs)
			///
			/// \brief	Copies the specified FixedArray to this one.
			///
			/// \author	Markus
			/// \date	22.01.2010
			///
			/// \param	[in]	rhs	The right hand side object. 
			////////////////////////////////////////////////////////////////////////////////////////////////////
			void Copy(const FixedArray<T> & rhs);



			tSize m_size;

			T * m_elements;

		private:

	};





	///
	template<class T>
	inline void FixedArray<T>::Delete()
	{
		if(this->m_elements != NULL)
		{
			r_darray(this->m_elements);

			this->m_elements = 0;
		}

		this->m_size = 0;
	}


	///
	template<class T>
	inline void FixedArray<T>::Alloc(tSize size)
	{
		if(size > 0)
		{
			this->m_elements = r_narray(T,size);

			this->m_size = size;
		}
	}


	///
	template<class T>
	inline void FixedArray<T>::Copy(const Helper::FixedArray<T> &rhs)
	{
		this->Alloc(rhs.m_size);

		for(tIndex i = 0; i < this->m_size; i++)
		{
			this->m_elements[i] = rhs.m_elements[i];
		}
	}





	///
	template<class T>
	inline FixedArray<T>::FixedArray():
	m_size(0),
		m_element(0)
	{

	}


	///
	template<class T>
	inline FixedArray<T>::FixedArray(tSize size):
	m_size(size)
	{
		this->Alloc(size);
	}


	///
	template<class T>
	inline FixedArray<T>::FixedArray(tSize size, const T &element):
	m_size(size)
	{
		this->Alloc(size);

		for(tIndex i = 0; i < this->m_size; i++)
		{
			this->m_elements[i] = element;
		}
	}


	///
	template<class T>
	inline FixedArray<T>::FixedArray(const Helper::FixedArray<T> &rhs):
	m_size(size),
		m_element(rhs.m_elements)
	{
		this->Copy(rhs);
	}





	///
	template<class T>
	inline void FixedArray<T>::operator =(const Helper::FixedArray<T> &rhs)
	{
		this->Delete();

		this->Copy(rhs);
	}


	///
	template<class T>
	inline bool FixedArray<T>::operator ==(const Helper::FixedArray<T> &rhs) const
	{
		if(this->m_size != rhs.m_size)
			return false;

		for(tIndex i = 0; i < this->m_size; i++)
		{
			if(!(this->m_elements[i] == rhs.m_elements[i]))
				return false;
		}

		return true;
	}


	///
	template<class T>
	inline bool FixedArray<T>::operator !=(const Helper::FixedArray<T> &rhs) const
	{
		return !(*this == rhs);
	}


	///
	template<class T>
	inline const T & FixedArray<T>::operator [] (tIndex index) const 
	{
		return this->m_elements[index];
	}


	///
	template<class T>
	inline T & FixedArray<T>::operator [] (tIndex index)
	{
		return this->m_elements[index];
	}





	///
	template<class T>
	void FixedArray<T>::SetSize(tSize newSize)
	{
		this->Delete();

		this->Alloc(newSize);
	}


	///
	template<class T>
	tSize FixedArray<T>::Size() const 
	{
		return this->m_size;
	}


	///
	template<class T>
	bool FixedArray<T>::IsEmpty() const 
	{
		return (this->m_elements == NULL);
	}


	///
	template<class T>
	void FixedArray<T>::Reset(tSize newsize)
	{
		T * result = r_narray(T, newsize);

		for(tIndex i = 0; i < this->m_size; i++)
		{
			result[i] = this->m_elements[i];
		}

		this->m_elements = result;
	}



	///
	template<class T>
	void FixedArray<T>::Clear()
	{
		this->Delete();
	}


	///
	template<class T>
	void FixedArray<T>::Fill(const T & element)
	{
		for(tIndex i = 0; i < this->m_size; i++)
		{
			this->m_elements[i] = element;
		}
	}


	///
	template<class T>
	void FixedArray<T>::Fill(tSize start, tSize num, const T &element)
	{
#ifdef RE_DEBUG_MODE
		r_assert(start + num > this->m_size);
#endif

		for(tIndex i = 0; i < num; i++)
		{
			this->m_elements[i + start] = element;
		}
	}



	///
	template<class T>
	typename FixedArray<T>::Iterator FixedArray<T>::Begin() const
	{
		return this->m_elements;
	}


	///
	template<class T>
	typename FixedArray<T>::Iterator FixedArray<T>::End() const
	{
		return this->m_elements + this->m_size;
	}


	///
	template<class T>
	typename FixedArray<T>::Iterator FixedArray<T>::Find(const T &element)
	{
		for(tIndex i = 0; i < this->m_size; i++)
		{
			if(this->m_elements[i] == element)
				return &(this->m_elements[i]);
		}

		return NULL;
	}


	///
	template<class T>
	tIndex FixedArray<T>::FindIndex(const T &element)
	{
		for(tIndex i = 0; i < this->m_size; i++)
		{
			if(this->m_elements[i] == element)
				return i;
		}

		return InvalidIndex;
	}


	///
	template<class T>
	tIndex FixedArray<T>::BinarySearchIndex(const T &element) const
	{
		tSize num = this->Size();

		if(num > 0)
		{
			tIndex half;
			tIndex lo = 0;
			tIndex hi = num - 1;
			tIndex mid;

			while(lo <= hi)
			{
				if(0 != (half = num/2))
				{
					mid = lo + ((num & 1) ? half : (half - 1));

					if(element < this->m_elements[mid])
					{
						hi = mid - 1;
						num = num & 1 ? half : half - 1;
					}
					else if(element > this->m_elements[mid])
					{
						lo = mid + 1;
						num = half;
					}
					else
					{
						return mid;
					}
				}
				else if(0 != num)
				{
					if(element != this->m_elements[lo])
					{
						return InvalidIndex;
					}
					else
					{
						return lo;
					}
				}
				else
				{
					break;
				}
			}
		}
		
		return InvalidIndex;
	}


	///
	template<class T>
	Helper::Array<T> FixedArray<T>::GetAsArray() const
	{
		Helper::Array<T> result;

		for(tIndex i = 0; i < this->m_size; i++)
		{
			result.Add(this->m_elements[i]);
		}

		return result;
	}

}

#endif // fixedarray_h__